The present invention is directed to an improved periodic wireless data broadcast and, more particularly, to (1) an improved method of arranging data on a periodic broadcast and (2) an improved signal structure for such broadcasts.
Delivering information via wireless transmission is becoming increasingly popular. As seen in FIG. 1, information, such as stock prices, traffic information, weather reports, airline schedules, and sports scores, may be broadcast from a single source, such as a service provider 30 (not unlike a cellular phone service provider) to a number of recipients (users) 32 via a wireless transmission media. These media may be, for example, paging networks, FM subcarrier networks, cellular phone networks, and PCS (personal communications services) networks. This application will refer to the media simply as a xe2x80x9cwireless media networkxe2x80x9d.
A user 32 may be a person having a wireless terminal 34, such as a personal digital assistant (PDA), as is illustrated in FIG. 1. (The wireless terminal 34 is often referred to as a xe2x80x9cclientxe2x80x9d, and the ultimate human recipient of the information is referred to as a xe2x80x9cuserxe2x80x9d.) A PDA is typically a laptop or palmtop computer connected to a wireless media network. The wireless terminal 34 usually is not connected to any direct power source, but rather runs on either conventional or rechargeable batteries. Because wireless terminals are often used away from the home or office, it is an important consideration of a wireless terminal user to maximize the length of time that the terminal may operate without having to change or recharge batteries. Thus, it is important to minimize the power consumption necessary for the client to receive, decode, and display information received over the wireless data network, thus increasing the useful life of the battery.
One method of transmitting information over a wireless network is to broadcast the information periodically. This method is well-known and has been discussed in Imielinski et al, xe2x80x9cEnergy Efficient Indexing on Airxe2x80x9d, Proc. ACM SIGMOD Conference, May, 1994. In August 1994 we noted the similarity of this method to the method of writing data on a standard rotating magnetic disk, and thus called the method an xe2x80x9cairdiskxe2x80x9d by analogy. Subsequently, Zdonik et al, xe2x80x9cAre xe2x80x98Disks in the Airxe2x80x99 Just Pie in the Sky?xe2x80x9d, Proc. IEEE Workshop on Mobile Computing Systems and Applications, Dec. 8-9, 1994, also noted this similarity, and called this method a xe2x80x9cbroadcast diskxe2x80x9d. An xe2x80x9cairdiskxe2x80x9d is a periodic transmission of data over a wireless network. It is called an airdisk because it may be theoretically compared to a rotating data disk, as will be illustrated below. FIG. 2 shows a periodic broadcast 40 having a number of transmissions (the arrow indicates increasing time). A first transmission 50 includes the following sequence of topics: stock prices 51, traffic 52, weather 53, airline schedules 54, and sports scores 55. After the transmission 50 is complete, a new transmission 60 is immediately sent, beginning with, in this example, stock information 61, traffic 62, etc. Each transmission may begin with a preamble 56, 66 indicating the beginning of a transmission. The preamble may be followed by an index 57, 67 which indicates the location of the beginning of each topic in the transmission. Each topic 51-55, 61-65 may begin with a topic header 58, 68 which indicates the start of a topic. Each transmission may end with a trailer 59, 69 indicating the end of a transmission.
Although the example in FIG. 2 shows the broadcast is composed of different items defined as topics of information (stock prices 51, traffic 52, etc.), it could just as well be the case that the broadcast contains items which relate to a single topic. For example, FIG. 2 could refer to stock prices only, with a first transmission including the following sequence of items which relate to a single topic: IBM price, NYNEX price, HP price, and so on. This discussion often refers to xe2x80x9ctopicsxe2x80x9d for illustration. In most instances, however, the illustration is equally applicable to smaller items, such as information about particular stocks, traffic conditions on certain roadways, or weather conditions for a certain geographic region.
The broadcast 40 is periodic because each transmission is immediately followed by another. As seen in FIG. 3, the periodic broadcast 40 of FIG. 2 may be theoretically compared to a revolving disk 70 (i.e., such as a computer or optical disk) and a read head 80 (i.e., such as a magnetic or optical head) (the arrow indicates the direction of disk rotation). The disk in this illustration is separated into five radial portions called sectors. These sectors contain stock 71, traffic 72, weather 73, airline 74, and sports 75 information, respectively. Protocol related portions of the signal such as the preamble, the index, the headers, and the trailer are omitted for simplicity. After a complete rotation of the disk 70, the same sector is presented to the head 80 for reading. Similar to a computer disk, the periodic broadcast 40 may be updated by the service provider 30 so that subsequent rotations may include revised, additional, or altered data; and the data may be presented in a different sequence.
Much of the information on the airdisk is dynamicxe2x80x94for example, stock prices, sports scores, weather, and traffic conditions may change throughout the day. Thus, after a period of time some information transmitted in a periodic broadcast may become xe2x80x9cstalexe2x80x9d and is of little use to the user 32 (i.e., hours old stock prices during active trading). Thus, the amount of time it takes a client 34 to access all of the desired information (referred to as xe2x80x9caccess latencyxe2x80x9d) is one measure of performance for an airdisk transmission. Also, because many periodic broadcast clients may be wireless terminals, where power efficiency is a major concern, power a consumption may be minimized by the ordering of the data in the transmission. This is illustrated in FIGS. 4a and 4b. 
Using the rotating disk analogy, FIGS. 4a and 4b show the importance of data ordering in instances where the transmission is not indexed and indexed, respectively. Using an index in a periodic transmission is discussed in the Imielinski et al. paper cited above.
Where the transmission has no index, the receiver, such as a wireless terminal 34, must be on at all times to determine whether it is receiving information it is interested in so that it may read this information. This constant monitoring of the incoming transmission inefficiently consumes power. Alternatively, if all of the information sections are of equal sizexe2x80x94and thus of equal time lengthxe2x80x94the terminal 34 could be programmed to turn on at the beginning of each section and quickly determine if the section includes data desired to be read. This alternative conserves power but may be impractical because the sections may be of differing lengths and because the information is dynamic, each section may be a different length each broadcast. (Unlike a physical disk, an airdisk may increase or decrease in size if information is added or deleted to a topic.) If the sections are certain types of data items, such as stock prices, however, the items may be arranged to have identical lengths.
An index may be provided at the beginning of each transmission giving the sequence of topics and the location of the beginning of each topic in the upcoming transmission. This is advantageous because it allows the terminal 34 to be xe2x80x9coffxe2x80x9d (i.e., consuming a reduced amount of power) except when desired information is being broadcast. This reduces the xe2x80x9conxe2x80x9d time for the wireless transmitter 34 and conserves power. An index may be disadvantageous, however, because it requires additional data to be included in the broadcast. This makes the airdisk xe2x80x9clargerxe2x80x9d and takes a longer time to transmit the entire periodic broadcast.
FIG. 4a illustrates the access latency for an unindexed airdisk 70xe2x80x2. A user 32 is interested in sports and traffic information. At the random time shown in this figure, the read head 80 is positioned over airline information 74xe2x80x2. A first time delayxe2x80x94a rotational latency 82xe2x80x94occurs in the time it takes the disk to rotate to a topic of interest (in this illustration, sports is the first topic of interest presented to the read head 80). The next time period is the read time 84 (illustrated by a dashed line), that is, the time that the information about the desired topic is being read from the disk 70xe2x80x2 by the read head 80. A second time delayxe2x80x94a topic (or item) spread 86xe2x80x94occurs during the time it takes the disk to rotate to the last topic of interest. The final time period is the final topic read time 88 when the final information about the topic of interest is read by the read head 80. Because information is read on-the-fly (i.e., it is read relatively instantaneously as it rotates past the read head 80); the total access latency would be the same if some or all of the topics between sports and traffic were also desired. That is, in this illustration, the access latency and the terminal xe2x80x9conxe2x80x9d time would have been the same if the user wanted stock information 71xe2x80x2, as well. Thus, in this example, the access latency for all of the desired topics is about three quarters of a rotation (about three quarters of a complete transmission).
FIG. 4b illustrates the access latency for an indexed airdisk 70xe2x80x3. Note that the airdisk 70xe2x80x3 includes an index 90. Again, the topics the user 32 is interested in are sports 75xe2x80x3 and traffic 72xe2x80x3. At the random time shown in this figure, the read head 80 is positioned over airline information 74xe2x80x3. A first time delayxe2x80x94a rotational latency 92 for the index 90xe2x80x94occurs in the time it takes the disk to rotate to the index 90. Note that the sports information 75xe2x80x3, which is the user is interested in, was not read because the index 90 has not yet been read and therefore the client 34 does not know the location of the sports information. Thus, the sports information 75xe2x80x3 is passed over until the next rotation (i.e., the next transmission). The next time period is the index read time 94 (illustrated by a dashed line). This is the time that the index 90 is being read by the read head 80. A second time delayxe2x80x94a topic (or item) reach 96xe2x80x94occurs during the time the disk rotates to the last topic of interest (here, sports 75xe2x80x3). Note that during the topic reach 96, information about topics of interest (traffic 72xe2x80x3) is read. The traffic information read time 97 (illustrated by a dashed line) is part of the topic reach 96. Because reading is done on-the-fly, this read time 97 does not affect the topic reach 96. The final time period of the access latency is the final topic read time 98 when information about the final topic of interest (sports 75xe2x80x3) is read by the read head 80. Because of the index 90, the terminal 43 is only xe2x80x9conxe2x80x9d when information about topics of interest is being read. The total xe2x80x9conxe2x80x9d time for the terminal 34 is the index read time 94, the traffic information read time 97, and the sports information read time 98. Thus, the total on-time is reduced from that of the non-indexed airdisk of FIG. 4a. On the other hand, the total access latency is much greater in this illustration, and exceeds the time for a complete rotation due to the index rotational access latency 92.
xe2x80x9cAccess latencyxe2x80x9d as used in this patent application, refers to the total time for:
a) the rotational latency;
b) the first item read time;
c) the item reach or spread (including any read times); and
d) the last item read time.
Actual data disks have another time delay as illustrated in FIG. 4c. A disk 70xe2x80x2xe2x80x3 may be arranged with data stored in sectors divided by annular tracks. In FIG. 4c, the disk 70xe2x80x2xe2x80x3 is divided into five sectors and three tracks. This creates fifteen areas for storing data (i.e., data 0-data 14). The additional time delay is due to positioning the read head 80 over the appropriate track when the sector is positioned by the read head 80. This time delay does not apply to the disks 70xe2x80x2, 70xe2x80x3 because they have only one track, nor to airdisks because there is no head to be physically positioned over a track.
One way to reduce the average access latency for a number of users 32 would be to order the topics on the transmission so that the average access latency for all users 32 is minimized. The rotational latency and data transfer times are fixed once the set of information in a given rotation (transmission) is decided. However, the topic spread (or topic reach) may still be varied by knowing in advance the sequence of the topics on the disk. If the topics which the users 32 desire to read is known in advance (how this may be done is described below), a disk layout (i.e., a transmission) may be chosen to reduce the average topic spread or reach for all users. That is, if many users are interested in stock and traffic information, these users"" access latency may, be minimized by placing these two topics first.
We, the inventors of the present invention, however, have proven that the algorithm minimizing the access latency for a number of users 32 each requesting two or more items is xe2x80x9cNP-completexe2x80x9d (non deterministic polynomial time complete). This means that the algorithm is mathematically intractable to calculate. This is discussed in Jain and Werth, xe2x80x9cAirdisks and AirRAID: Modeling and Scheduling Periodic Wireless Data Broadcast (Extended Abstract)xe2x80x9d, presented on Apr. 27, 1995 at Rutgers University Winlab Workshop. The contents of this paper are incorporated herein by reference.
Another problem associated with periodic wireless data broadcasts is that an increased data amount results in a xe2x80x9cbiggerxe2x80x9d airdisk. That is, the time for a complete periodic transmission increases. This longer transmission time results in a longer potential access latency which, as discussed above, is undesirable due to the dynamic nature of some of the information in the broadcast. Also, in many existing wireless spectrum transmission channels, data communications must coexist with voice communications. The wireless spectrum is divided into multiple channels, where the bandwidth is optimized for voice or short message communications (such as paging).
For example, a Wireless Access Communications Systems (WACS) has been proposed by Bellcore in a paper entitled xe2x80x9cGeneric Criteria for Version O.I. Wireless Access Communications Systems (WACS)xe2x80x9d, Technical Advisory TA-NWT-001313, Issue 1, July 1992. This system uses transmissions having frames divided into time slots. Each frame has eight time slots. Each time slot is 2.5 msec and is capable of holding 32 kb/sec. (Other wireless transmission media may be capable of broadcasting at only 16 kb/sec.) Thus, in one minute a broadcast could transmit 1.92 Mbits. However, data xe2x80x9coverheadxe2x80x9d, such as packet framing, indexes, preambles, headers, trailers, and the like reduce the amount of actual data in a transmission, effectively reducing the speed of a transmission. Thus, a 1 megabyte (i.e., 8 megabit) transmission may take as long as eight minutes. Moreover, as the amount of data in the transmission increases, the transmission time (the rotation time) increases linearly. The increased transmission time (the rotation time) results in an increased access latency. Because the value of some information decreases with time (i.e., stock prices during active trading), a high access latency is unacceptable. Thus, it is desirable to increase the xe2x80x9cstorage capacityxe2x80x9d of an airdisk, so that a large number of bytes are transmitted per unit time.
Thus, it is an object of the present invention to provide a method for arranging the information on a periodic transmission which reduces the average access latency for clients of a wireless data service provider.
It is another object of the present invention to provide a transmission signal structure which increases an airdisk""s storage capacity without incurring undesirable access latency penalties.
It is yet another object of the present invention to provide an efficient periodic wireless transmission having adequate error correction.
These objects are achieved by a periodic wireless data transmission according to the present invention. The order of topics or items on an airdisk may be arranged by sorting the topics or items to be transmitted onto a list in order of popularity. In one preferred embodiment, this list may be revised by comparing each adjacent pair of topics on the list. The topics"" positions on the list are exchanged if the exchange decreases the average latency for all users. This is repeated for all of the topics on the list.
In a second preferred embodiment, users are provided with a number of votes to select items or topics of interest, which may be xe2x80x9ccastxe2x80x9d in any manner the user chooses (even casting fractions of one vote). This prevents users interested in a few items or topics from being xe2x80x9coutvotedxe2x80x9d by users interested in many items or topics. One way this may be done, for example, is by providing each user with one xe2x80x9cpopularity votexe2x80x9d, which may be used on one or more items. If more than one item is chosen, the value of the user""s vote is decreased to the fraction 1/x, where x is the total number of items the user selected. The value of all the votes for an item or topics is added in determining the order of popularity.
In a third preferred embodiment, after the popularity list is sorted, the comparison of adjacent topics or items is performed iteratively. For example, once the most popular topic is determined, the process is repeated for all users not interested in the most popular topic or item. This is repeated until all of the topics or items have been sorted.
The transmission structure may also be arranged so that the transmission combines a number of transmission channels to obtain greater aggregate capacity. This may be done, for example, by structuring the transmissions to be theoretically comparable to a plurality of xe2x80x9cstripedxe2x80x9d data disks. Data disk striping is writing adjacent data units across an array of synchronized rotating disks. This allows data to be accessed in parallel. In a preferred embodiment, data is xe2x80x9cstripedxe2x80x9d onto a wireless media transmission by writing adjacent data units across a number of frequencies of an FDMA transmission. This allows a client to receive the information of interest simultaneously from a plurality of frequencies.